/*-------------------------------------------------------------------------
 *
 * network_spgist.c
 *	  网络类型的 SP-GiST 支持。
 *
 * 我们首先按地址族 (IPv4 或 IPv6) 拆分 inet 索引项。
 * 如果给定内部元组下方的所有条目都属于同一族，
 * 我们识别它们的公共前缀，并按地址的下一个位拆分，
 * 以及是否它们的 masklens 超过了公共前缀的长度。
 *
 * 一个同时拥有 IPv4 和 IPv6 子项的内部元组具有空前缀
 * 和正好两个节点，第一个是 IPv4，第二个是 IPv6。
 *
 * 否则，前缀是表示公共前缀的 CIDR 值，
 * 并且恰好有四个节点。 节点编号 0 和 1 是用于与前缀
 * 相同 masklen 的地址，而节点编号 2 和 3 是用于有更大
 * masklen 的地址。 （我们不允许元组包含 masklen
 * 小于其前缀的条目。）节点编号 0 和 1 由公共前缀之后的
 * 地址的下一个位区分，节点编号 2 和 3 也是如此。
 * 如果地址族中没有更多位，所有内容都进入节点 0
 * （这可能会导致创建一个 allTheSame 元组）。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/utils/adt/network_spgist.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <sys/socket.h>

#include "access/spgist.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/inet.h"


static int	fc_inet_spg_node_number(const inet *fc_val, int fc_commonbits);
static int	fc_inet_spg_consistent_bitmap(const inet *fc_prefix, int fc_nkeys,
									   ScanKey fc_scankeys, bool fc_leaf);

/*
 * SP-GiST 配置函数
 */
Datum inet_spg_config(PG_FUNCTION_ARGS)
{
	/* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
	spgConfigOut *fc_cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

	fc_cfg->prefixType = CIDROID;
	fc_cfg->labelType = VOIDOID;
	fc_cfg->canReturnData = true;
	fc_cfg->longValuesOK = false;

	PG_RETURN_VOID();
}

/*
 * SP-GiST 选择函数
 */
Datum inet_spg_choose(PG_FUNCTION_ARGS)
{
	spgChooseIn *fc_in = (spgChooseIn *) PG_GETARG_POINTER(0);
	spgChooseOut *fc_out = (spgChooseOut *) PG_GETARG_POINTER(1);
	inet	   *fc_val = DatumGetInetPP(fc_in->datum),
			   *fc_prefix;
	int			fc_commonbits;

	/*
	 * 如果我们正在查看一个按地址系列拆分的元组，请选择
	 * 适当的子节点。
	 */
	if (!fc_in->hasPrefix)
	{
		/* allTheSame 对于这样的元组是不可能的 */
		Assert(!fc_in->allTheSame);
		Assert(fc_in->nNodes == 2);

		fc_out->resultType = spgMatchNode;
		fc_out->result.matchNode.nodeN = (ip_family(fc_val) == PGSQL_AF_INET) ? 0 : 1;
		fc_out->result.matchNode.restDatum = InetPGetDatum(fc_val);

		PG_RETURN_VOID();
	}

	/* 否则必须按前缀拆分 */
	Assert(fc_in->nNodes == 4 || fc_in->allTheSame);

	fc_prefix = DatumGetInetPP(fc_in->prefixDatum);
	fc_commonbits = ip_bits(fc_prefix);

	/*
	 * 我们不能将不同系列的地址放在同一个内部节点下，所以如果
	 * 新值的系列不同，我们必须拆分。
	 */
	if (ip_family(fc_val) != ip_family(fc_prefix))
	{
		/* 设置 2 节点元组 */
		fc_out->resultType = spgSplitTuple;
		fc_out->result.splitTuple.prefixHasPrefix = false;
		fc_out->result.splitTuple.prefixNNodes = 2;
		fc_out->result.splitTuple.prefixNodeLabels = NULL;

		/* 确定现有数据应放入哪个节点 */
		fc_out->result.splitTuple.childNodeN =
			(ip_family(fc_prefix) == PGSQL_AF_INET) ? 0 : 1;

		fc_out->result.splitTuple.postfixHasPrefix = true;
		fc_out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(fc_prefix);

		PG_RETURN_VOID();
	}

	/*
	 * 如果新值与现有前缀不匹配，我们必须拆分。
	 */
	if (ip_bits(fc_val) < fc_commonbits ||
		bitncmp(ip_addr(fc_prefix), ip_addr(fc_val), fc_commonbits) != 0)
	{
		/* 确定拆分元组的新前缀长度 */
		fc_commonbits = bitncommon(ip_addr(fc_prefix), ip_addr(fc_val),
								Min(ip_bits(fc_val), fc_commonbits));

		/* 设置 4 节点元组 */
		fc_out->resultType = spgSplitTuple;
		fc_out->result.splitTuple.prefixHasPrefix = true;
		fc_out->result.splitTuple.prefixPrefixDatum =
			InetPGetDatum(cidr_set_masklen_internal(fc_val, fc_commonbits));
		fc_out->result.splitTuple.prefixNNodes = 4;
		fc_out->result.splitTuple.prefixNodeLabels = NULL;

		/* 确定现有数据应放入哪个节点 */
		fc_out->result.splitTuple.childNodeN =
			fc_inet_spg_node_number(fc_prefix, fc_commonbits);

		fc_out->result.splitTuple.postfixHasPrefix = true;
		fc_out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(fc_prefix);

		PG_RETURN_VOID();
	}

	/*
	 * 一切正常，选择要下降到的节点。（如果此元组被标记为
	 * allTheSame，核心代码将忽略我们对 nodeN 的选择；但我们不需要
	 * 在此处显式考虑该情况。）
	 */
	fc_out->resultType = spgMatchNode;
	fc_out->result.matchNode.nodeN = fc_inet_spg_node_number(fc_val, fc_commonbits);
	fc_out->result.matchNode.restDatum = InetPGetDatum(fc_val);

	PG_RETURN_VOID();
}

/*
 * GiST PickSplit 方法
 */
Datum inet_spg_picksplit(PG_FUNCTION_ARGS)
{
	spgPickSplitIn *fc_in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
	spgPickSplitOut *fc_out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
	inet	   *fc_prefix,
			   *fc_tmp;
	int			fc_i,
				fc_commonbits;
	bool		fc_differentFamilies = false;

	/* 用第一个项目初始化前缀 */
	fc_prefix = DatumGetInetPP(fc_in->datums[0]);
	fc_commonbits = ip_bits(fc_prefix);

	/* 检查其余项目以发现最小公共前缀长度 */
	for (fc_i = 1; fc_i < fc_in->nTuples; fc_i++)
	{
		fc_tmp = DatumGetInetPP(fc_in->datums[fc_i]);

		if (ip_family(fc_tmp) != ip_family(fc_prefix))
		{
			fc_differentFamilies = true;
			break;
		}

		if (ip_bits(fc_tmp) < fc_commonbits)
			fc_commonbits = ip_bits(fc_tmp);
		fc_commonbits = bitncommon(ip_addr(fc_prefix), ip_addr(fc_tmp), fc_commonbits);
		if (fc_commonbits == 0)
			break;
	}

	/* 不需要标签；分配输出数组 */
	fc_out->nodeLabels = NULL;
	fc_out->mapTuplesToNodes = (int *) palloc(sizeof(int) * fc_in->nTuples);
	fc_out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * fc_in->nTuples);

	if (fc_differentFamilies)
	{
		/* 设置 2 节点元组 */
		fc_out->hasPrefix = false;
		fc_out->nNodes = 2;

		for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
		{
			fc_tmp = DatumGetInetPP(fc_in->datums[fc_i]);
			fc_out->mapTuplesToNodes[fc_i] =
				(ip_family(fc_tmp) == PGSQL_AF_INET) ? 0 : 1;
			fc_out->leafTupleDatums[fc_i] = InetPGetDatum(fc_tmp);
		}
	}
	else
	{
		/* 设置 4 节点元组 */
		fc_out->hasPrefix = true;
		fc_out->prefixDatum =
			InetPGetDatum(cidr_set_masklen_internal(fc_prefix, fc_commonbits));
		fc_out->nNodes = 4;

		for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
		{
			fc_tmp = DatumGetInetPP(fc_in->datums[fc_i]);
			fc_out->mapTuplesToNodes[fc_i] = fc_inet_spg_node_number(fc_tmp, fc_commonbits);
			fc_out->leafTupleDatums[fc_i] = InetPGetDatum(fc_tmp);
		}
	}

	PG_RETURN_VOID();
}

/*
 * SP-GiST 查询一致性检查用于内部元组
 */
Datum inet_spg_inner_consistent(PG_FUNCTION_ARGS)
{
	spgInnerConsistentIn *fc_in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
	spgInnerConsistentOut *fc_out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
	int			fc_i;
	int			fc_which;

	if (!fc_in->hasPrefix)
	{
		Assert(!fc_in->allTheSame);
		Assert(fc_in->nNodes == 2);

		/* 确定需要访问哪些子节点 */
		fc_which = 1 | (1 << 1);

		for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
		{
			StrategyNumber fc_strategy = fc_in->scankeys[fc_i].sk_strategy;
			inet	   *fc_argument = DatumGetInetPP(fc_in->scankeys[fc_i].sk_argument);

			switch (fc_strategy)
			{
				case RTLessStrategyNumber:
				case RTLessEqualStrategyNumber:
					if (ip_family(fc_argument) == PGSQL_AF_INET)
						fc_which &= 1;
					break;

				case RTGreaterEqualStrategyNumber:
				case RTGreaterStrategyNumber:
					if (ip_family(fc_argument) == PGSQL_AF_INET6)
						fc_which &= (1 << 1);
					break;

				case RTNotEqualStrategyNumber:
					break;

				default:
					/* 所有其他操作只能匹配相同系列的地址 */
					if (ip_family(fc_argument) == PGSQL_AF_INET)
						fc_which &= 1;
					else
						fc_which &= (1 << 1);
					break;
			}
		}
	}
	else if (!fc_in->allTheSame)
	{
		Assert(fc_in->nNodes == 4);

		/* 确定需要访问哪些子节点 */
		fc_which = fc_inet_spg_consistent_bitmap(DatumGetInetPP(fc_in->prefixDatum),
										   fc_in->nkeys, fc_in->scankeys, false);
	}
	else
	{
		/* 必须访问所有节点；我们假设它们少于 32 个 */
		fc_which = ~0;
	}

	fc_out->nNodes = 0;

	if (fc_which)
	{
		fc_out->nodeNumbers = (int *) palloc(sizeof(int) * fc_in->nNodes);

		for (fc_i = 0; fc_i < fc_in->nNodes; fc_i++)
		{
			if (fc_which & (1 << fc_i))
			{
				fc_out->nodeNumbers[fc_out->nNodes] = fc_i;
				fc_out->nNodes++;
			}
		}
	}

	PG_RETURN_VOID();
}

/*
 * SP-GiST 查询一致性检查用于叶子元组
 */
Datum inet_spg_leaf_consistent(PG_FUNCTION_ARGS)
{
	spgLeafConsistentIn *fc_in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
	spgLeafConsistentOut *fc_out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
	inet	   *fc_leaf = DatumGetInetPP(fc_in->leafDatum);

	/* 所有测试都是准确的。 */
	fc_out->recheck = false;

	/* 叶子就是它的样子... */
	fc_out->leafValue = InetPGetDatum(fc_leaf);

	/* 使用公共代码来应用测试。 */
	PG_RETURN_BOOL(fc_inet_spg_consistent_bitmap(fc_leaf, fc_in->nkeys, fc_in->scankeys,
											  true));
}

/*
 * 计算节点编号（在 4 节点，单系列内部索引元组中）
 *
 * 该值必须具有与节点前缀相同的系列，且
 * commonbits 是前缀的掩码长度。我们根据公共位之后的下一个地址位使用奇数或偶数节点，
 * 根据值的掩码长度是否大于 commonbits 使用低节点或高节点。
 */
static int fc_inet_spg_node_number(const inet *fc_val, int fc_commonbits)
{
	int			fc_nodeN = 0;

	if (fc_commonbits < ip_maxbits(fc_val) &&
		ip_addr(fc_val)[fc_commonbits / 8] & (1 << (7 - fc_commonbits % 8)))
		fc_nodeN |= 1;
	if (fc_commonbits < ip_bits(fc_val))
		fc_nodeN |= 2;

	return fc_nodeN;
}

/*
 * 计算与查询一致的节点编号的位图
 *
 * 这可以在 4 路内元组或叶元组中使用。
 * 在后者的情况下，我们应该返回布尔结果（0 或 1），
 * 而不是位图。
 *
 * 这个定义相当奇怪，但是内部和叶一致性检查
 * 大部分是共同的，似乎最好将它们保留在一个函数中。
 */
static int fc_inet_spg_consistent_bitmap(const inet *fc_prefix, int fc_nkeys, ScanKey fc_scankeys,
						   bool fc_leaf)
{
	int			fc_bitmap;
	int			fc_commonbits,
				fc_i;

	/* 初始化结果以允许访问所有子节点 */
	if (fc_leaf)
		fc_bitmap = 1;
	else
		fc_bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);

	fc_commonbits = ip_bits(fc_prefix);

	for (fc_i = 0; fc_i < fc_nkeys; fc_i++)
	{
		inet	   *fc_argument = DatumGetInetPP(fc_scankeys[fc_i].sk_argument);
		StrategyNumber fc_strategy = fc_scankeys[fc_i].sk_strategy;
		int			fc_order;

		/*
		 * 检查 0: 不同的家族
		 *
		 * 匹配的家族对任何策略都没有帮助。
		 */
		if (ip_family(fc_argument) != ip_family(fc_prefix))
		{
			switch (fc_strategy)
			{
				case RTLessStrategyNumber:
				case RTLessEqualStrategyNumber:
					if (ip_family(fc_argument) < ip_family(fc_prefix))
						fc_bitmap = 0;
					break;

				case RTGreaterEqualStrategyNumber:
				case RTGreaterStrategyNumber:
					if (ip_family(fc_argument) > ip_family(fc_prefix))
						fc_bitmap = 0;
					break;

				case RTNotEqualStrategyNumber:
					break;

				default:
					/* 对于所有其他情况，我们可以确保没有匹配 */
					fc_bitmap = 0;
					break;
			}

			if (!fc_bitmap)
				break;

			/* 其他检查在不同的家族中毫无意义。 */
			continue;
		}

		/*
		 * 检查 1: 网络位计数
		 *
		 * 网络位计数（ip_bits）有助于检查叶子是否适合子网络
		 * 和超网络运算符。在非叶节点中，我们知道每个子节点
		 * 值具有更大的 ip_bits，因此在某些情况下
		 * 我们也可以避免下探。
		 *
		 * 这个检查比检查地址位的开销更小，因此我们
		 * 在此之前进行，但在基本
		 * 比较策略中必须在之后进行，因为 ip_bits 仅在
		 * 公共网络位相同的情况下影响它们的结果。
		 */
		switch (fc_strategy)
		{
			case RTSubStrategyNumber:
				if (fc_commonbits <= ip_bits(fc_argument))
					fc_bitmap &= (1 << 2) | (1 << 3);
				break;

			case RTSubEqualStrategyNumber:
				if (fc_commonbits < ip_bits(fc_argument))
					fc_bitmap &= (1 << 2) | (1 << 3);
				break;

			case RTSuperStrategyNumber:
				if (fc_commonbits == ip_bits(fc_argument) - 1)
					fc_bitmap &= 1 | (1 << 1);
				else if (fc_commonbits >= ip_bits(fc_argument))
					fc_bitmap = 0;
				break;

			case RTSuperEqualStrategyNumber:
				if (fc_commonbits == ip_bits(fc_argument))
					fc_bitmap &= 1 | (1 << 1);
				else if (fc_commonbits > ip_bits(fc_argument))
					fc_bitmap = 0;
				break;

			case RTEqualStrategyNumber:
				if (fc_commonbits < ip_bits(fc_argument))
					fc_bitmap &= (1 << 2) | (1 << 3);
				else if (fc_commonbits == ip_bits(fc_argument))
					fc_bitmap &= 1 | (1 << 1);
				else
					fc_bitmap = 0;
				break;
		}

		if (!fc_bitmap)
			break;

		/*
		 * 检查 2: 公共网络位
		 *
		 * 将可用的公共前缀位与查询进行比较，但不能超出
		 * 查询的子网掩码或所表示值中的最小子网掩码。
		 * 如果这些位与查询不匹配，我们可以
		 * 消除某些情况。
		 */
		fc_order = bitncmp(ip_addr(fc_prefix), ip_addr(fc_argument),
						Min(fc_commonbits, ip_bits(fc_argument)));

		if (fc_order != 0)
		{
			switch (fc_strategy)
			{
				case RTLessStrategyNumber:
				case RTLessEqualStrategyNumber:
					if (fc_order > 0)
						fc_bitmap = 0;
					break;

				case RTGreaterEqualStrategyNumber:
				case RTGreaterStrategyNumber:
					if (fc_order < 0)
						fc_bitmap = 0;
					break;

				case RTNotEqualStrategyNumber:
					break;

				default:
					/* 对于所有其他情况，我们可以确保没有匹配 */
					fc_bitmap = 0;
					break;
			}

			if (!fc_bitmap)
				break;

			/*
			 * 当公共位不匹配时，剩余检查毫无意义。
			 */
			continue;
		}

		/*
		 * 检查 3: 下一网络位
		 *
		 * 如果可用，我们可以使用参数的下一网络位来过滤掉
		 * 分支 2 或 3。
		 *
		 * 这个检查对搜索的性能很重要。没有它，结果
		 * 也会正确。
		 */
		if (fc_bitmap & ((1 << 2) | (1 << 3)) &&
			fc_commonbits < ip_bits(fc_argument))
		{
			int			fc_nextbit;

			fc_nextbit = ip_addr(fc_argument)[fc_commonbits / 8] &
				(1 << (7 - fc_commonbits % 8));

			switch (fc_strategy)
			{
				case RTLessStrategyNumber:
				case RTLessEqualStrategyNumber:
					if (!fc_nextbit)
						fc_bitmap &= 1 | (1 << 1) | (1 << 2);
					break;

				case RTGreaterEqualStrategyNumber:
				case RTGreaterStrategyNumber:
					if (fc_nextbit)
						fc_bitmap &= 1 | (1 << 1) | (1 << 3);
					break;

				case RTNotEqualStrategyNumber:
					break;

				default:
					if (!fc_nextbit)
						fc_bitmap &= 1 | (1 << 1) | (1 << 2);
					else
						fc_bitmap &= 1 | (1 << 1) | (1 << 3);
					break;
			}

			if (!fc_bitmap)
				break;
		}

		/*
		 * 剩余检查仅适用于基本比较策略。此
		 * 测试依赖于 stratnum.h 中定义的策略编号排序。
		 */
		if (fc_strategy < RTEqualStrategyNumber ||
			fc_strategy > RTGreaterEqualStrategyNumber)
			continue;

		/*
		 * 检查 4: 网络位计数
		 *
		 * 此时，我们知道前缀的公共网络位和参数是相同的，
		 * 因此我们可以继续检查 ip_bits。
		 */
		switch (fc_strategy)
		{
			case RTLessStrategyNumber:
			case RTLessEqualStrategyNumber:
				if (fc_commonbits == ip_bits(fc_argument))
					fc_bitmap &= 1 | (1 << 1);
				else if (fc_commonbits > ip_bits(fc_argument))
					fc_bitmap = 0;
				break;

			case RTGreaterEqualStrategyNumber:
			case RTGreaterStrategyNumber:
				if (fc_commonbits < ip_bits(fc_argument))
					fc_bitmap &= (1 << 2) | (1 << 3);
				break;
		}

		if (!fc_bitmap)
			break;

		/* 当 ip_bits 不同时，剩余检查毫无意义。 */
		if (fc_commonbits != ip_bits(fc_argument))
			continue;

		/*
		 * 检查 5: 下一主机位
		 *
		 * 如果可用，我们可以使用参数的下一主机位来过滤掉
		 * 分支 0 或 1。
		 *
		 * 这个检查对搜索的性能很重要。没有它，结果
		 * 也会正确。对于叶节点没有必要运行此检查，因为我们必须在下一步检查整个地址。
		 */
		if (!fc_leaf && fc_bitmap & (1 | (1 << 1)) &&
			fc_commonbits < ip_maxbits(fc_argument))
		{
			int			fc_nextbit;

			fc_nextbit = ip_addr(fc_argument)[fc_commonbits / 8] &
				(1 << (7 - fc_commonbits % 8));

			switch (fc_strategy)
			{
				case RTLessStrategyNumber:
				case RTLessEqualStrategyNumber:
					if (!fc_nextbit)
						fc_bitmap &= 1 | (1 << 2) | (1 << 3);
					break;

				case RTGreaterEqualStrategyNumber:
				case RTGreaterStrategyNumber:
					if (fc_nextbit)
						fc_bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
					break;

				case RTNotEqualStrategyNumber:
					break;

				default:
					if (!fc_nextbit)
						fc_bitmap &= 1 | (1 << 2) | (1 << 3);
					else
						fc_bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
					break;
			}

			if (!fc_bitmap)
				break;
		}

		/*
		 * 检查 6: 整个地址
		 *
		 * 这是基本比较策略正确性的最后检查。它
		 * 仅适用于叶条目。
		 */
		if (fc_leaf)
		{
			/* 通过使用所有地址位重新进行排序比较 */
			fc_order = bitncmp(ip_addr(fc_prefix), ip_addr(fc_argument),
							ip_maxbits(fc_prefix));

			switch (fc_strategy)
			{
				case RTLessStrategyNumber:
					if (fc_order >= 0)
						fc_bitmap = 0;
					break;

				case RTLessEqualStrategyNumber:
					if (fc_order > 0)
						fc_bitmap = 0;
					break;

				case RTEqualStrategyNumber:
					if (fc_order != 0)
						fc_bitmap = 0;
					break;

				case RTGreaterEqualStrategyNumber:
					if (fc_order < 0)
						fc_bitmap = 0;
					break;

				case RTGreaterStrategyNumber:
					if (fc_order <= 0)
						fc_bitmap = 0;
					break;

				case RTNotEqualStrategyNumber:
					if (fc_order == 0)
						fc_bitmap = 0;
					break;
			}

			if (!fc_bitmap)
				break;
		}
	}

	return fc_bitmap;
}
